Computer systems maintain lists of information in a wide variety of applications. For example, many mainframe computers maintain a list, or queue, of processes to be executed by one or more processing units. Such process queues are often maintained by the operating system in a reserved memory area. As another example, many computers that employ magnetic disk storage devices maintain a list of available or unused storage locations on the disk. One common form of list employed in many of these applications is known in the art as a linked list. A linked list typically comprises a plurality of stored elements, or nodes, linked sequentially through the use of pointers. A linked list may be either singularly or doubling linked. With a singularly linked list, each stored element points only to the next subsequent element of the list. With a doubly linked list, each element points to the next subsequent element as well as the immediately preceding element of the list. Because pointers are used to link each successive element, the elements do not have to be stored in contiguous memory locations.
Each element of a singularly linked list typically comprises a data portion and a pointer to the next subsequent element of the list. Each element represents a single entry, or item, in the list and contains information relevant to that item. For example, in the case of a process queue for maintaining a list of processes to be executed by a computer system, each element of the list represents a single process and contains information relevant to the execution of that process, such as its priority, etc.
A singularly linked list has a "head", i.e., the first element of the list, and a defined end point, i.e., the last element of the list. Typically, the end of the list is established by setting the pointer of the last element to a null value. A special pointer is often defined in order to identify the head of a linked list.
Unfortunately, computer systems are susceptible to failure or unexpected shutdown in a number of situations, such as power outages and equipment failures. In these situations, partial or even complete memory loss is not uncommon. Consequently, information relating to the status or structure of a linked list, particularly information identifying the head of the list, can be lost. In such cases, it will be necessary to reestablish the head of the linked list before normal system operation can resume.
One particular situation in which information concerning the head of a queue may be lost arises in connection with the diagnoses of hardware and/or software problems in UNISYS A Series mainframe computers. UNISYS A Series computers provide an ability to dump the contents of main memory to a storage device, such as a peripheral tape drive, so that the contents of memory can be analyzed with a specialized diagnostic tool. A Series systems maintain a "ready queue" which, in general, is a singularly linked list of processes that are "ready" to be executed, but are awaiting to be scheduled on an available processor. On certain classes of A series computers, a special purpose instruction processor, called the Task Control Processor (TCP), is responsible for process scheduling and maintaining the ready queue. The ready queue is not managed by the operating system, and therefore, the data structure is not maintained in normal system memory. As a result, dumping the contents of normal system memory for analysis purposes does not provide a copy of the ready queue. However, the memory dump process does gather state information from the TCP, including information identifying the state of all processes in existence at the time of the memory dump. Specifically, for each process, information concerning the state (e.g., active, blocked, ready, etc.) is provided, and in the case of those processes that are indicated as being "ready", a pointer to the next process in the ready queue is provided. Thus, the individual elements and linkages of the ready queue are intact and available for analysis. Unfortunately, however, the process at the head of the ready queue is not explicitly identified. For proper diagnosis of hardware and software problems, the head of the ready queue must be reestablished.
As the foregoing illustrates, in many situations it may be necessary to reconstruct or reestablish the head of a linked list. Accordingly, methods are needed for quickly and efficiently establishing the head of a linked list in cases where such information has been lost. One technique for determining the head of a linked list, but which the inventors have found to be disadvantageous, involves accessing each stored element of the list and traversing the list from that element to the end of list. For each element, a count of the number of linkages originating from that element to the end of the list is generated. The element having the largest linkage count will, of course, be the head of the list. Unfortunately, generating a linkage count for each element by traversing the list from that element to the end of the list requires on the order of N.sup.2 memory accesses, where N is the number of elements in the list. With large lists, the time required to establish the head of the list using this technique becomes prohibitive. Consequently, more efficient and faster techniques for establishing the head of a singularly linked list are needed. The methods of the present invention satisfy this need.